package main

import (
	"fmt"
	"os"
	"runtime/debug"
	"strconv"
	"time"
)

func main() {
	board := [][]byte{
		{5, 3, 4, 6, 7, 0, 0, 0, 0},
		{6, 0, 0, 1, 9, 5, 0, 0, 0},
		{0, 9, 8, 0, 0, 0, 0, 6, 0},
		{8, 0, 0, 0, 6, 0, 0, 0, 3},
		{4, 0, 0, 8, 0, 3, 0, 0, 1},
		{7, 0, 0, 0, 2, 0, 0, 0, 6},
		{0, 6, 0, 0, 0, 0, 2, 8, 0},
		{0, 0, 0, 4, 1, 9, 0, 0, 5},
		{0, 0, 0, 0, 8, 0, 0, 7, 9},
	}
	m := cannotmodify(board)
	fmt.Println(m)
	solveSudoku(&board, m)
	display(board)

}

// 返回不能修改的数据
func cannotmodify(board [][]byte) map[string]int {
	m := make(map[string]int)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != 0 {
				str := strconv.Itoa(i) + "-" + strconv.Itoa(j)
				m[str] = 1
			}
		}
	}
	return m
}

func next(board *[][]byte) (int, int) {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if get(board, i, j) == 0 {
				return i, j
			}
		}
	}
	return -1, -1
}

func accept(board *[][]byte) bool {
	x, y := next(board)
	if x != -1 && y != -1 {
		return false
	}
	return true
}
func set(board *[][]byte, x, y int, v byte) {
	b := *board
	b[x][y] = v
}

func get(board *[][]byte, x, y int) byte {
	b := *board
	return b[x][y]
}

func solveSudoku(board *[][]byte, m map[string]int) {
	defer PanicHandler()
	if accept(board) {
		return
	}
	x, y := next(board)

	for i := 1; i <= 9; i++ {
		set(board, x, y, byte(i))
		if isValidSudoku(*board) {
			solveSudoku(board, m)
		} else {
			set(board, x, y, 0)
		}
	}
	x, y = prev(board, m)
	if contains(m, x, y) {
		return
	}

	set(board, x, y, 0)
	display(*board)
}

func PanicHandler() {
	exeName := os.Args[0] //获取程序名称

	now := time.Now()  //获取当前时间
	pid := os.Getpid() //获取进程ID

	time_str := now.Format("20060102150405")                          //设定时间格式
	fname := fmt.Sprintf("%s-%d-%s-dump.log", exeName, pid, time_str) //保存错误信息文件名:程序名-进程ID-当前时间（年月日时分秒）
	fmt.Println("dump to file ", fname)

	f, err := os.Create(fname)
	if err != nil {
		return
	}
	defer f.Close()

	if err := recover(); err != nil {
		f.WriteString(fmt.Sprintf("%v\r\n", err)) //输出panic信息
		f.WriteString("========\r\n")
	}

	f.WriteString(string(debug.Stack())) //输出堆栈信息
}


func prev(board *[][]byte, m map[string]int) (int, int) {
	x, y := next(board)

	if y == 8 && x != 0 {
		x--
	} else {
		y--
	}
	if contains(m, x, y) {
		x, y = prev2(board, x, y, m)
	}

	if x < 0 || y < 0 {
		return -1, -1
	}
	return x, y
}

func prev2(board *[][]byte, x, y int, m map[string]int) (int, int) {
	if y == 8 && x != 0 {
		x--
	} else {
		y--
	}

	if contains(m, x, y) {
		x, y = prev2(board, x, y, m)
	}
	return x, y
}

func contains(m map[string]int, x, y int) bool {
	str := strconv.Itoa(x) + "-" + strconv.Itoa(y)
	_, ok := m[str]
	return ok
}

func display(board [][]byte) {
	// display
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board); j++ {
			fmt.Printf("%v ", board[i][j])
		}
		fmt.Println()
	}
	fmt.Println()
}

func isValidSudoku(board [][]byte) bool {

	result := true
	var columns []byte
	var grids1 []byte
	var grids2 []byte
	var grids3 []byte
	for i := 0; i < 9; i++ {
		if i/3 == 1 {
			if len(grids1) == 9 {
				result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)
				//fmt.Println(grids1)
				//fmt.Println(grids2)
				//fmt.Println(grids3)
				grids1 = []byte{}
				grids2 = []byte{}
				grids3 = []byte{}
			}
		} else if i/3 == 2 {
			if len(grids1) == 9 {
				result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)
				//fmt.Println(grids1)
				//fmt.Println(grids2)
				//fmt.Println(grids3)
				grids1 = []byte{}
				grids2 = []byte{}
				grids3 = []byte{}
			}
		}
		for j := 0; j < 9; j++ {
			if j/3 == 0 { // 遇到3，遇到6
				grids1 = append(grids1, board[i][j])
			} else if j/3 == 1 {
				grids2 = append(grids2, board[i][j])
			} else if j/3 == 2 {
				grids3 = append(grids3, board[i][j])
			}
		}
	}
	result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)

	//fmt.Println(grids1)
	//fmt.Println(grids2)
	//fmt.Println(grids3)

	for i := 0; i < len(board); i++ {
		columns = []byte{}
		result = result && isValid(board[i]) // 行检查

		for j := 0; j < len(board); j++ {
			columns = append(columns, board[j][i])
		}
		result = result && isValid(columns) // 列检查
	}
	return result
}

func isValid(arr []byte) bool {
	m := make(map[byte]byte, len(arr))
	for _, v := range arr {
		if v != byte(0) {
			if v < 1 || v > 9 {
				return false
			}
			_, ok := m[v]
			if ok {
				return false
			}
			m[v] = v
		}
	}
	return true
}
